#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        
        sort(nums.begin(), nums.end(), Cmp); // 从大到小排序

        stack<int> greater;
        stack<int> lesser;

        int sumGre = 0;
        int sumLes = 0;

        for (int counter = 0; counter < nums.size(); ++counter) {
            greater.push(nums[counter]);
            sumGre += nums[counter];
            
            ++counter;
            if (counter == nums.size()) {
                break;
            }

            lesser.push(nums[counter]);
            sumLes += nums[counter];
        }

        while (sumLes < sumGre && sumGre > 0) {
            sumLes += greater.top();
            sumGre -= greater.top();
            lesser.push(greater.top());
            greater.pop();
        }

        if (sumLes == sumGre) {
            return true;
        }

        if (sumLes > sumGre) {
            lesser.pop(); // 先把导致超大的数字弹出，但是不能减去
            while (sumLes != sumGre && !lesser.empty()) {               // 然后将较小的数字弹出，如果sumless < sumGre, 保留，
                if (sumLes - lesser.top() >= sumGre + lesser.top()) {
                    sumLes -= lesser.top();
                    sumGre += lesser.top();
                }
                lesser.pop();
            }
                           // 如果sumLess > sumGre ,减去
                           // 直到lesser为空，或者两者相等
            if (sumGre == sumLes) {
                return true;
            }

        }

        return false;
    }
private:
    static bool Cmp(int a, int b)
    {
        return a >= b;
    }
};

int main()
{
    Solution sol;
    vector<int> vec{1};
    cout<<sol.canPartition(vec)<<endl;
}